public class Main2 {
    /**
     * 二分查找-I
     */
    public int search (int[] nums, int target) {
        // write code here
        int start = 0;
        int len = nums.length - 1;
        while(start <= len) {
            int mid = (start + len) / 2;
            if(nums[mid] == target) {
                return mid;
            }
            if(nums[mid] > target) {
                len = mid - 1;
            }else {
                start = mid + 1;
            }
        }
        return -1;
    }

    /**
     * 二维数组中的查找
     */
    public boolean Find (int target, int[][] array) {
        // write code   here
        if(array.length == 0) {
            return false;
        }
        int n = array.length;
        if(array[0].length == 0) {
            return false;
        }
        int m = array[0].length;
        for(int i = n - 1, j = 0; i >= 0 && j < m; ) {
            if(array[i][j] > target) {
                i--;
            }else if ( array[i][j] < target) {
                j++;
            }else {
                return true;
            }
        }
        return false;
    }

    /**
     * 寻找峰值
     */
    public int findPeakElement (int[] nums) {
        // write code here
        int left = 0;
        int right = nums.length - 1;
        while(left < right) {
            int mid = (left + right) / 2;
            //右边是往下，不一定有坡峰
            if(nums[mid] > nums[mid + 1]) {
                right = mid;
            } else {
                //右边是往上，一定能找到坡峰
                left = mid + 1;
            }

        }
        return right;
    }

    /**
     * 旋转数组的最小数字
     */
    public int minNumberInRotateArray (int[] nums) {
        // write code here
        int n = 0;
        int m = nums.length - 1;
        if(nums[n] < nums[m]) {
            return nums[n];
        }
        while(m >= 0 && nums[n] >= nums[m]) {
            n = m;
            m = m - 1;
        }
        return nums[n];
    }
    public int minNumberInRotateArray2 (int[] nums) {
        // write code here
        if(nums.length == 0) {
            return 0;
        }
        int i = 0;
        int j = nums.length - 1;
        while(i < j) {
            //找到数组的中点
            int m = (i + j) / 2;
            //m在左排序数组中，旋转点在[m+1，j]中
            if(nums[m] > nums[j]) {
                i = m + 1;
            } else if (nums[m] < nums[j]) {
                //m在右排序数组中，旋转点在[i,m]中
                j = m;
            } else {
                j--;
            }
        }
        return nums[i];
    }
    /**
     * 比较版本号
     */
    public int compare (String version1, String version2) {
        // write code here
        int n1 = version1.length();
        int n2 = version2.length();
        int i = 0;
        int j = 0;
        while(i < n1 || j < n2) {
            long num1 = 0;
            while(i < n1 && version1.charAt(i) != '.') {
                num1 = num1 * 10 + (version1.charAt(i) - '0');
                i++;
            }
            //跳过点
            i++;
            long num2 = 0;
            while(j < n2 && version2.charAt(j) != '.') {
                num2 = num2 * 10 + (version2.charAt(j) - '0');
                j++;
            }
            //跳过点
            j++;
            //比较数字大小
            if(num1 > num2) {
                return 1;
            }
            if(num1 < num2) {
                return -1;
            }
        }
        return 0;
    }
    public int compare2 (String version1, String version2) {
        // write code here
        //比较，划分
        String[] nums1 = version1.split("\\.");
        String[] nums2 = version2.split("\\.");
        for(int i = 0; i < nums1.length || i < nums2.length; i++) {
            String str1 = i < nums1.length ? nums1[i] : "0";
            String str2 = i < nums2.length ? nums2[i] : "0";
            long num1 = 0;
            //字符串转数字
            for(int j = 0; j < str1.length(); j++) {
                num1 = num1 * 10 + (str1.charAt(j) - '0');
            }
            long num2 = 0;
            for(int j = 0; j < str2.length(); j++) {
                num2 = num2 * 10 + (str2.charAt(j) - '0');
            }
            //比较数字大小
            if(num1 > num2) {
                return 1;
            }
            if(num1 < num2) {
                return -1;
            }
        }
        return 0;
    }
}
